package com.lyj.sc.paixu;

import java.util.Arrays;

/**
 * @Author: liyangjing
 * @Date: 2022/03/07/15:19
 * @Description:
 */
public class QuickSortTest {

    public static void main(String[] args) {
        int [] a ={36,25,78,35,96,45,20,11};
//        int[] ints = sortArray(a);
//        System.out.println(Arrays.toString(ints));
        shuangquick(a,0,a.length-1);
    }
    //双边循环
    private static void shuangquick(int[] a, int low, int high) {
        if(low>=high){
            return;
        }
        sort2(a,low,high);
    }
    public static void  sort2(int[] a, int low, int high){
        if(low>=high){
            return;
        }
        int pv = a[low];
        int i = low;
        int j = high;
        while (i<j){
            while (i<j && pv<a[j]){
                j--;
            }
            while (i<j&& pv>=a[i]){
                i++;
            }
            swap(a,i,j);
        }
        swap(a,low,j);
        System.out.println(Arrays.toString(a));
        sort(a,low,j-1);
        sort(a,j+1,high);
    }
    //单边循环
    private static void quick(int[] a, int low, int high) {
        if(low>=high){
            return;
        }
        sort(a,low,high);
    }
    public static void  sort(int[] a, int low, int high){
        if(low>=high){
            return;
        }
        //基准点
        int pv = a[high];
        int i = low;
        for(int j = low;j<=high;j++){
            if(a[j]<pv){
                swap(a,i,j);
                i++;
            }
        }
        swap(a,i,high);
        System.out.println(Arrays.toString(a));
        sort(a,low,i-1);
        sort(a,i+1,high);
    }

    //交换
    public static void swap(int []arr ,int i, int j){
        int temp;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}
